The present disclosure relates generally to decoding data encoded with variable length codes.
Variable length coding (VLC) is almost ubiquitously used in video/audio compression standards to achieve efficient data compression. Though variable length coding is also used in encoding other syntax elements in a video/audio stream, the majority of bits in a bitstream are used for encoding transform coefficients. Accordingly, on the playback side, reconstruction of the audio/video conventionally requires two steps. First, variable length decoding (VLD) is applied to the encoded bitstream to obtain codewords. Then various (and usually large numbers of) look-up tables are used to recover the transform coefficients. Then other steps follow to reconstruct the video/audio based on the transform coefficients, such as inverse quantization, inverse transform, motion compensation, de-blocking, and the like.
Almost in any video/audio compression standard, some variable length code (VLC) is used to take advantage of statistical information to effectively reduce the data amount. The compression is achieved by using shorter bit strings to represent frequently occurring data while assigning longer bit strings to less frequently occurring data. A typical VLC decoding table in its raw format without any processing usually has a format including two or more columns. One column lists the encoded bit-strings, which are of variable length. One or more other columns list the value(s) of data words, such as syntax element(s) or transform coefficients, that the bit-strings represent.
Without loss of generality, a VLC decoding table can also be thought of having two columns with one column listing the variable-length bit-strings and the other column listing an integer number conventionally called “CodeNum”. The CodeNum is used as an index to look up another table that contains one or more columns with each column indicating the value of a specific syntax element or transform coefficient defined in the standard's bit-stream format. While variable length codes are used to encode many kinds of syntax elements in a bitstream, the majority of the bits are used to encode transform coefficients in a bitstream.
Like other processing in decoding a bit-stream, reconstructing the transform coefficients takes a considerable number of computation cycles, which is typically around 30% of the total cycles needed, though the exact number can change from stream to stream depending on the bit-rate and other complexities in encoding the stream. So speeding up this processing will generally speed up the video decompression as a whole, which generally burdens the processors or specially designed hardware embedded in a device for multimedia related applications.
As is implied by its conceptual components, reconstructing the transform coefficients is conventionally done in two separate steps. In the first step, the variable length bit string is decoded to generate a fixed length code called “CodeNum”, which is a very awkward operation in computer software or digital logic based hardware. In the second step, run-level tables or other kinds of tables are used to recover the transform coefficients based on the “CodeNum.” Different variable length decoding methods or different specially designed tables are usually used to encode the transform coefficients or syntax elements, depending on many factors such as whether these syntax elements are for luma or chroma, whether the macroblock (MB) is intra encoded or motion compensated, and the like.
Another complexity arises from the fact that different tables will usually be used to recover intermediate data which will be further used to eventually recover the transform coefficients once the “CodeNum” is available. The number of tables is typically in the range of dozens. For example, there are around 30 tables for Context-Adaptive Variable-Length Coding (CAVLC) in the widely used standard H.264, and there are around 20 run-level tables in the Chinese video compression standard named Audio Video Standard (AVS).
Still another complexity arises because many corner cases exist as deeply rooted in the very philosophy of the variable length encoding. These corner cases occur with a very low probability, but must be processed in order to correctly decode the bitstream. It is a challenge to provide full functionality without spending too much on these rarely occurring corner cases.